package d2;

import java.util.*;
public class Day1 {
    public static void main(String[] args) {

    }
    //验证栈序列
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> stack = new Stack<>();
        int j = 0;
        for(int i=0;i<pushed.length;i++) {
            int tmp = pushed[i];
            if(tmp == popped[j]) {
                j++;
                while(!stack.isEmpty()&&stack.peek()==popped[j]) {
                    stack.pop();
                    j++;
                }
            }else {
                stack.push(tmp);
            }
        }
        while(!stack.isEmpty()) {
            if(stack.pop()!=popped[j]) return false;
            j++;
        }
        return true;
    }
    //字符串解码
    public String decodeString(String s) {
        Stack<String> stack1 = new Stack<>();//存放字符串
        Stack<Integer> stack2 = new Stack<>();//存放数字
        stack1.push("");//防止越界
        int i=0;
        while(i<s.length()) {
            char ch = s.charAt(i);
            if(ch>='0'&&ch<='9') {
                //提取数字
                int tmp = (int)(ch-'0');
                i++;
                while(s.charAt(i)>='0'&&s.charAt(i)<='9') {
                    tmp *= 10;
                    tmp+=(int)(s.charAt(i)-'0');
                    i++;
                }
                stack2.push(tmp);
            }else if(ch=='[') {
                //提取字符串,放入栈1
                i++;
                StringBuilder tmp = new StringBuilder();
                while(s.charAt(i)>='a'&&s.charAt(i)<='z') {
                    tmp.append(s.charAt(i));
                    i++;
                }
                stack1.push(tmp.toString());
            }else if(ch==']') {
                i++;
                String tmp = stack1.pop();
                String ret = stack1.pop();//跟在栈顶元素后面
                int k = stack2.pop();
                while(k!=0) {
                    ret += tmp;
                    k--;
                }
                stack1.push(ret);
            }else {
                //提取字符串,放入栈顶元素后面
                StringBuilder tmp = new StringBuilder();
                while(i<s.length()&&s.charAt(i)>='a'&&s.charAt(i)<='z') {
                    tmp.append(s.charAt(i));
                    i++;
                }
                stack1.push(stack1.pop()+tmp.toString());
            }
        }
        return stack1.pop();
    }
}
